﻿namespace Leetcode.N0140;
public class Solution
{
    public IList<string> WordBreak(string s, IList<string> wordDict)
    {
        var flg = new bool[s.Length + 1];
        var indexList = new List<int>[s.Length + 1];
        var words = new HashSet<string>();
        foreach (var item in wordDict)
        {
            words.Add(item);
        }

        flg[0] = true;
        for (var i = 1; i <= s.Length; i++)
        {
            for (var j = 0; j < i; j++)
            {
                if (flg[j] && words.Contains(s.Substring(j, i - j)))
                {
                    if (indexList[i] == null)
                    {
                        indexList[i] = new List<int>();
                    }
                    indexList[i].Add(j);
                    flg[i] = true;
                }
            }
        }
        return this.GetString(s, indexList, s.Length) ?? new List<string>();
    }

    private IList<string> GetString(string s, List<int>[] indexList, int i)
    {
        var indexs = indexList[i];
        if (indexs == null || indexs.Count == 0)
        {
            return null;
        }
        var result = new List<string>();
        foreach (var index in indexs)
        {
            var pre = this.GetString(s, indexList, index);
            if (pre == null)
            {
                result.Add(s.Substring(index, i - index));
            }
            else
            {
                foreach (var ps in pre)
                {
                    result.Add($"{ps} {s.Substring(index, i - index)}");
                }
            }
        }
        return result;
    }

}
